import javax.swing.tree.TreeNode;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;

class Solution {
     static class TreeNode{
        int val;
        TreeNode left;
        TreeNode right;

         public int getVal() {
             return val;
         }

         public void setVal(int val) {
             this.val = val;
         }
     }
    public int rob(TreeNode root) {
        if(root==null){
            return 0;
        }
        Queue<TreeNode> queue=new LinkedList<>();
        queue.offer(root);
        int load=1;
        int answer1=0;
        int answer2=0;
        while(!queue.isEmpty()){
            int len=queue.size();
            while(len>0){
                TreeNode tmp=queue.poll();
                if(load%2==1){
                    answer1=answer1+tmp.val;
                }else{
                    answer2=answer2+tmp.val;
                }
                if(tmp.left!=null){
                    queue.offer(tmp.left);
                }
                if(tmp.right!=null){
                    queue.offer(tmp.right);
                }
                len--;
            }
            load++;
        }
        return answer1>=answer2?answer1:answer2;
    }
    public int count=0;
    public int coinChange(int[] coins, int amount) {
        if(amount==0){
            return 0;
        }
        if(coins.length==0){
            return -1;
        }
        int len=coins.length;
        int [] dp=new int[amount+1];
        Arrays.fill(dp,amount+1);
        dp[0]=0;
        for(int i=0;i<dp.length;i++){
            for(int coin:coins){
                if(i-coin<0){
                    continue;
                }
                dp[i]=Math.min(dp[i],1+dp[i-coin]);
            }

        }
        if(dp[amount]==amount+1){
            return -1;
        }
        return dp[amount];
    }
    public int numIslands(char[][] grid) {
        if(grid.length==0||grid==null){
            return 0;
        }
        int count=0;
        for(int i=0;i<grid.length;i++){
            for(int j=0;j<grid[0].length;j++){
                if(grid[i][j]=='1'){
                    dfs(grid,i,j);
                    count++;
                }
            }
        }
        return count;
    }
    public void dfs(char[][] grid,int i,int j){
        int right=grid.length;
        int down=grid[0].length;
        if(i<0||j<0||i>=right||j>=down||grid[i][j]=='0'){
            return;
        }
        grid[i][j]='0';
        dfs(grid,i,j-1);
        dfs(grid,i,j+1);
        dfs(grid,i+1,j);
        dfs(grid,i-1,j);
        return;
    }
}
